/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
  function plusUp (s, j) { // 向上转的函数 传入的参数是字符串和位置
    let str = s.split('')
    if (str[j] == '9') {
      str[j] = '0'
    } else {
      str[j] = Number(str[j]) + 1
    }
    return str.join('') // 返回新的字符串
  }
  function plusDown (s, j) {
    // 向下转的函数 传入的是字符串和位置
    let str = s.split('')
    if (str[j] == '0') {
      str[j] = '9'
    } else {
      str[j] = Number(str[j]) - 1
    }
    return str.join('')
  }
  // 防止走回头路 需要一个visited
  let visited = new Set()
  // 传入一个目标值 也就是这个的框架
  let q = [] // 创建一个队列
  let step = 0 // 记录要波动的次数
  q.push('0000') // 先把初始的位置放入队列中
  visited.add('0000') // 这个已经走过了
  while (q.length) {
    let size = q.length // 获得这个的大小
    for (let i = 0; i < size; i++) {
      // 逐步弹出每一个
      let cur = q.shift()
      // 判断是不是在死亡数组中
      if (deadends.includes(cur)) {
        continue
      }
      // 判断是否到达终点
      if (cur == target) {
        return step
      }
      // 把这个的相邻节点加入到队列中
      for (let j = 0; j < 4; j++) {
        let up = plusUp(cur, j)
        if (!visited.has(up)) {
          visited.add(up)
          q.push(up)
        }
        let down = plusDown(cur, j) // 获得向上向下的下一个字符
        if (!visited.has(down)) {
          visited.add(down)
          q.push(down)
        }
      }
    }
    // 这里计算步数
    step++ // 波动的次数+1
  }
  // 如果都穷举完了 就返回-1 说明找不到
  return -1
};
